1. Field of the Invention
The present invention relates to cryptographic systems, and more particularly to a method for computing a shared secret key.
2. Description of the Prior Art
Public key cryptography is used to provide security for information transmitted over public networks. Numerous cryptographic protocols are available to provide security, integrity and authentication. Their security is based on the apparent intractability of certain mathematical problems, such as integer factorization and the discrete logarithm problem. Public key schemes sometimes require more computing power than is generally available in constrained environments. Devices such as cellular phones, pagers, and smart cards usually have limited computing power and battery power available. In such environments, elliptic curve cryptography is particularly appealing since it provides security with parameters having a smaller number of bits. Computations are correspondingly faster because of the smaller amount of data that must be manipulated. In most cryptographic systems, parameters with a larger number of bits provide greater security at the cost of speed. Accordingly, there is a continual need to optimize cryptographic operations to run as quickly as possible, to make higher security implementations of the protocols feasible.
Digital signatures are a class of cryptographic protocols used to provide authentication. As in all public key systems, a sender has a private key and a public key. The public key is made available and authenticated to other users through a certificate or a directory. The sender signs a message using their private key, and a recipient is able to verify the signature by using the authentic public key. The mathematics of the scheme provides assurance that only the owner of the private key could generate a signature that will verify using the public key.
It is often of interest to share a key between two users of a public key cryptosystem. This key can be used to secure future communications using a symmetric key cryptosystem. The MQV (Menezes, Qu, Vanstone) protocol provides a method of sharing a key between two users of a public key cryptosystem that provides authentication of the key. This protocol is described in U.S. Pat. Nos. 5,761,305, 5,889,865, 5,896,455, and 6,122,736.
The following notation is used for the MQV protocol in a group G with a generator g
TermMeaningxAlice's ephemeral private keyyBob's ephemeral private keyRAAlice's ephemeral public key gxRBBob's ephemeral public key gyaAlice's long-term private keybBob's long-term private keyYAAlice's long-term public key gaYBBob's long-term public key gbsAAn intermediate component of the key computed by AlicesBAn intermediate component of the key computed by Bob
An early version of the MQV protocol for sharing a key between a pair of correspondents Alice and Bob proceeds as follows in the multiplicative group of a finite field having group order q.
1. Alice selects x at random from the interval 1 to q−1.
2. Alice computes RA=gx and sends it to Bob.
3. Bob selects y at random from the interval 1 to q−1.
4. Bob computes RB=gy and sends it to Alice.
5. Alice computes sA=(x+aRA)mod q and the shared secret K=(RB(YB)RB)sA.
6. Bob computes sB=(y+bRB)mod q and the shared secret K=(RA(YA)RA)sA.
The computationally intense parts of the key agreement protocol are the exponentiations that must be performed to determine K.
When the MQV protocol was standardized in the ANSI X9.62 and IEEE P1363 standards, a truncation operation was introduced to make the protocol more efficient. The MQV protocol as standardized uses a truncation operation to reduce the bit length of an exponent. The truncation operation is denoted by X and is defined as X=(X mod 280)+280. The protocol then proceeds as follows:
1. Alice selects x at random from the interval 1 to q−1.
2. Alice computes RA=gx and sends it to Bob.
3. Bob selects y at random from the interval 1 to q−1.
4. Bob computes RB=gy and sends it to Alice.
5. Alice computes sA=(x+a RA)mod q and the shared secret k=(RB(YB) RB)sA.
6. Bob computes sB=(y+b RB)mod q and the shared secret k=(RA(YA) RA)sB.
The use of the truncation operation speeds up computations since the exponent is shorter. However, this means that only half of the bits of the truncated values are used. It is believed that this truncation does not affect the security of the protocol, however it is generally preferable in the design of cryptographic methods to use as many bits of the random values and private values as possible.
A version of the MQV protocol uses an elliptic curve group as the underlying group G. The group generator is normally written as a point P, and additive notation is usually used instead of multiplication notation. In the Elliptic Curve MQV protocol, the value RA is then equal to xP, and the value RB is equal to yP. Each value RA, RB is thus a point on the elliptic curve. Since an elliptic curve point consists of two finite field elements, it is necessary to define a function π to convert an elliptic curve point into an integer. One typical function that is used is to interpret the bit string representing the first coordinate of the elliptic curve point as a bit string representing an integer. The component sA is equal to sA=(X+aπ(RA))mod q and the component sB is equal to sB=(y+bπ(RB))mod q. The shared key may then be expressed as K=sA(RB+π(RB)YB). The shared key K is an elliptic curve point, and usually it will be converted into another format for use in another protocol. The conversion often involves interpreting the bit string representing K as an integer. The corresponding two point multiplications are therefore necessary to compute the shared key and are also computationally intensive.
Accordingly, there is a need for a method of computing a shared key using the MQV protocols that obviates or mitigates at least some of the above disadvantages.